#include <stdio.h>
#include<malloc.h>
#include<stdlib.h>
char ch='y';
int i;
int k=0;
int m;
int siz =0;
int choice=1;
int o=0;
int size= 0;


struct node{
int value;
struct node * next;
};
struct node * first =NULL;


/* --------------------------------------------Reverse ------------------------------------------------------*/
struct node * reverse (struct node * first)
{
struct node *p,*t;
struct node * fir =NULL;
struct node * newptr;
for (p=first;p!=NULL;p=t)
{t=p->next;
newptr=p;
newptr->next= fir;
fir= newptr;

}

first= fir;
return first;
}

/* --------------------------------------------------Append-----------------------------------------------------------*/

struct node * append(struct node *first)
{
char ch ='y';
struct node *newptr,*p,*t;

while(ch=='y' || ch =='Y')
{
printf("\n Enter the  element");
scanf("%d",&m);
struct node * newptr;
newptr =malloc(sizeof(struct node));
newptr->value=m;

if(first!=NULL)
{
for(p=first;p->next!=NULL;p=p->next);
t=newptr;
p->next=t;
}

else if(first ==NULL)
{
first= newptr;
}

printf("\n Enter 'Y ' or 'y ' to continue inserting elements in list ");
scanf("%s",& ch);
}
return first;
}
/* --------------------------------------------------Display-----------------------------------------------------------*/

void display(struct node * first)
{ 
int y=0;
struct node * p;
printf("[");
for (p=first;p!=NULL;p=p->next)
{
if(p !=first && p!= NULL)
{printf(",");
}
printf("%d",p->value);


}
printf("]");

}


/* --------------------------------------------------Enter -----------------------------------------------------------*/



struct node * enter(struct node * first)
{
while(ch=='y' || ch== 'Y')

{

printf("\n Enter the  element");
scanf("%d",&m);
struct node * newptr;
newptr =malloc(sizeof(struct node));
newptr->value=m;
newptr ->next =first;
first =newptr;
printf("\n Enter 'Y ' or 'y ' to continue inserting elements in list ");
scanf("%s",& ch);
 

}
return first;
}


/* --------------------------------------------------extend take another list -----------------------------------------------------------*/


struct node  * extendlistnew(struct node * new)
{
char ch ='y';
struct node *newptr,*p,*t;

while(ch=='y' || ch =='Y')
{
printf("\n Enter the  element of extending list");
scanf("%d",&m);
struct node * newptr;
newptr =malloc(sizeof(struct node));
newptr->value=m;

if(new!=NULL)
{
for(p=new;p->next!=NULL;p=p->next);
t=newptr;
p->next=t;
}

else if(new ==NULL)
{
new= newptr;
}

printf("\n Enter 'Y ' or 'y ' to continue inserting elements in list .This is list which will be extended");
scanf("%s",& ch);
}

return new;
}



/* --------------------------------------------------Count-----------------------------------------------------------*/


int  count (struct node * first,int y)
{int val=0;

struct node *p,*t;

for (p=first;p!=NULL;p=p->next)
{
if(p->value ==y)
{val = val+1;

}
}

return val;
}
/* --------------------------------------------------Number of elements-----------------------------------------------------------*/

int  noofelements (struct node * first)
{
int siz;
struct node *p,*t;

for (p=first;p!=NULL;p=p->next)
{

siz = siz+1;


}

return siz;
}

/* --------------------------------------------------Search-----------------------------------------------------------*/

int  search (struct node * first,int t)
{int val=0;
int flag=0;
struct node *p;

for (p=first;p!=NULL;p=p->next)
{val=val+1;
if(p->value ==t)
{

flag=1;
break;
}


}
if (flag==1)
return val;
else 
return -9;
}
/* --------------------------------------------------Insert-----------------------------------------------------------*/

struct node * insert (struct node * first,int pos,int value)
{
int p,k;
struct node *t=first;
struct node *newptr ;

k =pos;
if(pos==0)
{
newptr=malloc(sizeof(struct node));
newptr->value= value;
newptr->next =first;
first=newptr;
return first;

}

else
{
for (p=0;p<k-1;p++)
{

t=t->next;
}
newptr=malloc(sizeof(struct node));
newptr->value= value;
newptr->next = t->next;
t->next =newptr;
return first;
}
}
/* --------------------------------------------------Remove-----------------------------------------------------------*/

struct node *remov(struct node *first, int val)
{
  struct node *cur =first;
struct node * prev =NULL;
      
  for (cur = first, prev = NULL;cur != NULL && cur->value != val; prev = cur, cur = cur->next);
 

if (cur == NULL) 
{
printf("Value not found");
return first;            
}

else if (cur == first)
{
first = first->next; 
return first;
}      



  else
   { prev->next = cur->next;  
  free(cur);
 return first;

}
}
/* --------------------------------------------------POP-----------------------------------------------------------*/


struct node *pop(struct node *first, int control)
{ int i=0;
int n=0;
  struct node *cur =first;
struct node * prev =NULL;
    int index =0;
 struct node * p= first; 

if(control ==-1)
{
printf("\n Now it will delete last element in list ");
for(cur=first,prev=NULL;cur->next!=NULL;cur=cur->next,prev=cur)
{n++;}
;
for(i=0;i<n;i++)
{
if(i ==n-1)
{
p->next = NULL;
}
p=p->next;
}
printf("\n Deleted value is %d ",cur->value );
free(prev);


return first;
}


else if(control ==-2)
{ 
printf("Deleted value is %d",first->value);
first=first->next;
return first;

}


 else 
{
     
  for (cur = first, prev = NULL;cur != NULL && index != control; prev = cur, cur = cur->next)
  
index++;
  ;
  if (cur == NULL) 
    return first;
            
  else if (cur == first)
    {
first = first->next; 
return first;
}  

    
  else
   {
printf("deleted value is %d",cur->value);
 prev->next = cur->next;  
  free(cur);
  return first;
}


}


}


/* --------------------------------------------------Sort-----------------------------------------------------------*/


struct node *sort(struct node *first)
{
  struct node *cur =first;
struct node * p ,*t,*k;
int temp;
      
  for (p=first;p!=NULL;p=p->next)
{
for(t=first;t!=NULL;t=t->next)
{
if(p->value <=t->value)

{
temp= (p->value);
(p->value) =(t->value);
(t->value)=temp;
}


}

}

  return first;
}

/* --------------------------------------------------Extend-----------------------------------------------------------*/


struct node * extend(struct node *first ,struct node * new)
{
char ch ='y';
struct node *p;
for (p=first;p->next!=NULL;p=p->next);

p->next = new;

return first;
}






/* --------------------------------------------------Now starts MAIN-----------------------------------------------------------*/

void main()
{
int ans,ans2,ans3,pos,o,u,con,val;
struct node * new =NULL;
while (choice !=12)
{
printf("\n Enter your choice");
printf("\n Enter 1 to append");
printf("\n Enter 2 to extend");
printf("\n Enter 3 to insert");   
printf("\n Enter 4 to remove");
printf("\n Enter 5 to pop");
printf("\n Enter 6 to find search or get index");
printf("\n Enter 7 to count");
printf("\n Enter 8 to sort");
printf("\n Enter 9 to reverse");
printf("\n Enter 10 to find no of elements in list");
printf("\n Enter 11 to display");
printf("\n Enter 12 to exit");


scanf("%d",&choice);
system("clear");
switch(choice)
{
case 1 :first= append(first);
        break;

case 2 : new= extendlistnew(new);
    first = extend(first,new);
new=NULL;
        break;

case 7: printf("\n Enter value to count");
scanf("%d",&u);

 ans = count(first,u);
printf("frequency  of element is %d",ans);
break;


case 3 :
printf("Enter index  at which insert");
scanf("%d",&pos);
printf("Enter value to insert");
scanf("%d",&val);

 first=insert(first,pos,val);
break;

case 5:
printf("\n Enter -1 to delete last element , -2 to delete first element,  or the index no to delete ");
scanf("%d",&con);
first=pop(first,con);
break;
case 4: 
printf("\n Enter value to delete");
scanf("%d",&val);
first=remov(first,val);
break;

case 6: printf("\n Enter value to search");
scanf("%d",&u);

 ans3 = search(first,u);
if(ans3!=-9)
printf("position  of element is %d",ans3-1);
else
printf("/n Value not found ");

break;

case 8: sort(first);
break;

case 9 : first =reverse (first);
         break;
case 10:ans2= noofelements(first);
printf("\n The no of elements are %d",ans2);
        break;

case 11 :display(first);
        break;
case 12 :exit(0);
break;
 default : printf("\n Enter a valid choice ");
break;

}

}
}

